| Authors |
Veselov Sergey Ivanovich, Candidate of physical and mathematical sciences, associate professor, sub-department of algebra, geometry and discrete mathematics, Institute of information technology, mathematics and mechanics, Lobachevsky State University of Nizhni Novgorod (23 Gagarina avenue, Nizhny Novgorod, Russia), veselov@vmk.unn.ru
Chirkov Aleksandr Yur'evich, Candidate of physical and mathematical sciences, associate professor, sub-department of algebra, geometry and discrete mathematics, Institute of information technology, mathematics and mechanics, Lobachevsky State University of Nizhni Novgorod (23 Gagarina avenue, Nizhny Novgorod, Russia), chir7@yandex.ru
Gribanov Dmitriy Vladimirovich, Assistent, sub-department of algebra,geometry and discrete mathematics, Institute of information technology, mathematics and mechanics, Lobachevsky State University of Nizhni Novgorod (23 Gagarina avenue, Nizhny Novgorod, Russia), dimitry.gribanov@gmail.com
|
| Abstract |
Background. The authors investigate the following generalization of the Diophantine equations aggregation: given Σj=1naijxj = ai, i = 1,...,m, with integer coefficients, we need to find integer multipliers f1,f2,...,fm such that all the vertices of the convex hull of integer non-negative solutions of the system are vertices of the convex hull of integer non-negative solutions of the equation Σmi=1fiΣnj=1aijxj = Σmi=1fiai.
Materials and methods. The study included well-known methods of linear programming and geometry of numbers.
Results. The existence of the generalized aggregating equation has been proved for any system of integer linear equations. A simple method to calculate the multipliers f1,f2,...,fm has been developed for systems with non negative coefficients. The obtainable lower bound has been received for the right-hand side of the generalized aggregating equation. The multidimensional knapsack problem has been reduced to the classical knapsack problem such that the right-hand side coefficient is less than at any of the existing aggregation methods.
Conclusions. The new approach to aggregation broadens the area of its application and reduces coefficients of the aggregating equation.
|
| References |
1. Shevchenko V. N. Kachestvennye voprosy tselochislennogo programmirovaniya [Qualitative problems of integer programming]. Moscow: Nauka, 1995, 192 p.
2. Veselov S. I. Kibernetika [Cybernetics]. 1985, no. 4, pp. 58–60.
3. Plateau G. and Guerch M. T. Lecture Notes in Control and Information Sciences. 1984, vol. 59, pp. 183–192.
4. Babaev D. A., Mamedov K. Sh. Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki [Journal of computing mathematics and mathematical physics]. 1978, vol. 18, no. 3, pp. 614–619.
5. Kannan R. Journal of the Association for Computing Machinery. 1983, vol. 30, no. 1, pp. 133–145.
6. Babayev D. A., Glover F. Discrete Applied Mathematics. 1984, vol. 8, no. 2, pp. 125–130.
7. Elimam A. A., Elmaghraby S. E. Discrete Applied Mathematics. 1985, vol. 12, no. 3, pp. 241–260.
8. Babayev D. A., Glover F., Ryan J. Informs Journal on Computing. 1997, vol. 9, no. 1, pp. 43–50.
9. Babayev D. A., Mardanov S. S. Discrete Applied Mathematics. 1994, vol. 50, no. 3, pp. 209–220.
10. Veselov S. I., Shevchenko V. N. Kibernetika [Cybernetics]. 1978, no. 4, pp. 78–79.
|
